#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ONLINE_JUDGE

#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

typedef long long LL;

const int N = 3e5+50;

int n, m;
int a[N];

int dat[2][N];

vector<int> e[N];
int ecnt;

tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> S;

int val[N];

void update(int x)
{
	int pos = S.order_of_key(make_pair(val[x], x));
	dat[0][x] = min(dat[0][x], pos);
	dat[1][x] = max(dat[1][x], pos);
}

int main(int argc, char const *argv[])
{
	scanf("%d%d", &n, &m);
	for (int i=0; i<n; ++i)
	{
		dat[0][i] = dat[1][i] = i;
	}
	for (int i=0; i<m; ++i)
	{
		scanf("%d", &a[i]);
		--a[i];
		dat[0][a[i]] = 0;
		if (i) e[i-1].push_back(a[i]);
	}

	for (int i=0; i<n; ++i)
	{
		S.insert(make_pair(0, i));
		val[i] = 0;
	}

	for (int i=0; i<m; ++i)
	{
		int cur = a[i];
		auto p = S.lower_bound(make_pair(val[cur], cur));
		S.erase(p);
		val[cur] = -i-1;
		S.insert(make_pair(val[cur], cur));

		for (int x : e[i])
		{
			update(x);
		}
	}
	for (int i=0; i<n; ++i)
		update(i);
	for (int i=0; i<n; ++i)
		printf("%d %d\n", dat[0][i] + 1, dat[1][i] + 1);
	return 0;
}